home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / emacs / emacs1857 / src_d2.zoo / source / regex.c < prev    next >
C/C++ Source or Header  |  1991-12-02  |  44KB  |  1,716 lines
  1. /* Extended regular expression matching and search.
  2.    Copyright (C) 1985 Free Software Foundation, Inc.
  3.  
  4.     This program is free software; you can redistribute it and/or modify
  5.     it under the terms of the GNU General Public License as published by
  6.     the Free Software Foundation; either version 1, or (at your option)
  7.     any later version.
  8.  
  9.     This program is distributed in the hope that it will be useful,
  10.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.     GNU General Public License for more details.
  13.  
  14.     You should have received a copy of the GNU General Public License
  15.     along with this program; if not, write to the Free Software
  16.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  
  18. In other words, you are welcome to use, share and improve this program.
  19. You are forbidden to forbid anyone else to use, share and improve
  20. what you give them.   Help stamp out software-hoarding!  */
  21.  
  22.  
  23. /* To test, compile with -Dtest.
  24.  This Dtestable feature turns this into a self-contained program
  25.  which reads a pattern, describes how it compiles,
  26.  then reads a string and searches for it.  */
  27.  
  28.  
  29. #ifdef emacs
  30.  
  31. /* The `emacs' switch turns on certain special matching commands
  32.  that make sense only in emacs. */
  33.  
  34. #include "config.h"
  35. #include "lisp.h"
  36. #include "buffer.h"
  37. #include "syntax.h"
  38.  
  39. #else  /* not emacs */
  40.  
  41. /*
  42.  * Define the syntax stuff, so we can do the \<...\> things.
  43.  */
  44.  
  45. #ifndef Sword /* must be non-zero in some of the tests below... */
  46. #define Sword 1
  47. #endif
  48.  
  49. #define SYNTAX(c) re_syntax_table[c]
  50.  
  51. #ifdef SYNTAX_TABLE
  52.  
  53. char *re_syntax_table;
  54.  
  55. #else
  56.  
  57. static char re_syntax_table[256];
  58.  
  59. static void
  60. init_syntax_once ()
  61. {
  62.    register int c;
  63.    static int done = 0;
  64.  
  65.    if (done)
  66.      return;
  67.  
  68.    bzero (re_syntax_table, sizeof re_syntax_table);
  69.  
  70.    for (c = 'a'; c <= 'z'; c++)
  71.      re_syntax_table[c] = Sword;
  72.  
  73.    for (c = 'A'; c <= 'Z'; c++)
  74.      re_syntax_table[c] = Sword;
  75.  
  76.    for (c = '0'; c <= '9'; c++)
  77.      re_syntax_table[c] = Sword;
  78.  
  79.    done = 1;
  80. }
  81.  
  82. #endif /* SYNTAX_TABLE */
  83. #endif /* not emacs */
  84.  
  85. #include "regex.h"
  86.  
  87. /* Number of failure points to allocate space for initially,
  88.  when matching.  If this number is exceeded, more space is allocated,
  89.  so it is not a hard limit.  */
  90.  
  91. #ifndef NFAILURES
  92. #define NFAILURES 80
  93. #endif NFAILURES
  94.  
  95. /* width of a byte in bits */
  96.  
  97. #define BYTEWIDTH 8
  98.  
  99. #ifndef SIGN_EXTEND_CHAR
  100. #define SIGN_EXTEND_CHAR(x) (x)
  101. #endif
  102.  
  103. static int obscure_syntax = 0;
  104.  
  105. /* Specify the precise syntax of regexp for compilation.
  106.    This provides for compatibility for various utilities
  107.    which historically have different, incompatible syntaxes.
  108.  
  109.    The argument SYNTAX is a bit-mask containing the two bits
  110.    RE_NO_BK_PARENS and RE_NO_BK_VBAR.  */
  111.  
  112. int
  113. re_set_syntax (syntax)
  114. {
  115.   int ret;
  116.  
  117.   ret = obscure_syntax;
  118.   obscure_syntax = syntax;
  119.   return ret;
  120. }
  121.  
  122. /* re_compile_pattern takes a regular-expression string
  123.    and converts it into a buffer full of byte commands for matching.
  124.  
  125.   PATTERN   is the address of the pattern string
  126.   SIZE      is the length of it.
  127.   BUFP        is a  struct re_pattern_buffer *  which points to the info
  128.         on where to store the byte commands.
  129.         This structure contains a  char *  which points to the
  130.         actual space, which should have been obtained with malloc.
  131.         re_compile_pattern may use  realloc  to grow the buffer space.
  132.  
  133.   The number of bytes of commands can be found out by looking in
  134.   the  struct re_pattern_buffer  that bufp pointed to,
  135.   after re_compile_pattern returns.
  136. */
  137.  
  138. #define PATPUSH(ch) (*b++ = (char) (ch))
  139.  
  140. #define PATFETCH(c) \
  141.  {if (p == pend) goto end_of_pattern; \
  142.   c = * (unsigned char *) p++; \
  143.   if (translate) c = translate[c]; }
  144.  
  145. #define PATFETCH_RAW(c) \
  146.  {if (p == pend) goto end_of_pattern; \
  147.   c = * (unsigned char *) p++; }
  148.  
  149. #define PATUNFETCH p--
  150.  
  151. #define EXTEND_BUFFER \
  152.   { char *old_buffer = bufp->buffer; \
  153.     if (bufp->allocated == (1<<16)) goto too_big; \
  154.     bufp->allocated *= 2; \
  155.     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
  156.     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
  157.       goto memory_exhausted; \
  158.     c = bufp->buffer - old_buffer; \
  159.     b += c; \
  160.     if (fixup_jump) \
  161.       fixup_jump += c; \
  162.     if (laststart) \
  163.       laststart += c; \
  164.     begalt += c; \
  165.     if (pending_exact) \
  166.       pending_exact += c; \
  167.   }
  168.  
  169. static int store_jump (), insert_jump ();
  170.  
  171. char *
  172. re_compile_pattern (pattern, size, bufp)
  173.      char *pattern;
  174.      int size;
  175.      struct re_pattern_buffer *bufp;
  176. {
  177.   register char *b = bufp->buffer;
  178.   register char *p = pattern;
  179.   char *pend = pattern + size;
  180.   register unsigned c, c1;
  181.   char *p1;
  182.   unsigned char *translate = (unsigned char *) bufp->translate;
  183.  
  184.   /* address of the count-byte of the most recently inserted "exactn" command.
  185.     This makes it possible to tell whether a new exact-match character
  186.     can be added to that command or requires a new "exactn" command. */
  187.      
  188.   char *pending_exact = 0;
  189.  
  190.   /* address of the place where a forward-jump should go
  191.     to the end of the containing expression.
  192.     Each alternative of an "or", except the last, ends with a forward-jump
  193.     of this sort. */
  194.  
  195.   char *fixup_jump = 0;
  196.  
  197.   /* address of start of the most recently finished expression.
  198.     This tells postfix * where to find the start of its operand. */
  199.  
  200.   char *laststart = 0;
  201.  
  202.   /* In processing a repeat, 1 means zero matches is allowed */
  203.  
  204.   char zero_times_ok;
  205.  
  206.   /* In processing a repeat, 1 means many matches is allowed */
  207.  
  208.   char many_times_ok;
  209.  
  210.   /* address of beginning of regexp, or inside of last \( */
  211.  
  212.   char *begalt = b;
  213.  
  214.   /* Stack of information saved by \( and restored by \).
  215.      Four stack elements are pushed by each \(:
  216.        First, the value of b.
  217.        Second, the value of fixup_jump.
  218.        Third, the value of regnum.
  219.        Fourth, the value of begalt.  */
  220.  
  221.   int stackb[40];
  222.   int *stackp = stackb;
  223.   int *stacke = stackb + 40;
  224.   int *stackt;
  225.  
  226.   /* Counts \('s as they are encountered.  Remembered for the matching \),
  227.      where it becomes the "register number" to put in the stop_memory command */
  228.  
  229.   int regnum = 1;
  230.  
  231.   bufp->fastmap_accurate = 0;
  232.  
  233. #ifndef emacs
  234. #ifndef SYNTAX_TABLE
  235.   /*
  236.    * Initialize the syntax table.
  237.    */
  238.    init_syntax_once();
  239. #endif
  240. #endif
  241.  
  242.   if (bufp->allocated == 0)
  243.     {
  244.       bufp->allocated = 28;
  245.       if (bufp->buffer)
  246.     /* EXTEND_BUFFER loses when bufp->allocated is 0 */
  247.     bufp->buffer = (char *) realloc (bufp->buffer, 28);
  248.       else
  249.     /* Caller did not allocate a buffer.  Do it for him */
  250.     bufp->buffer = (char *) malloc (28);
  251.       if (!bufp->buffer) goto memory_exhausted;
  252.       begalt = b = bufp->buffer;
  253.     }
  254.  
  255.   while (p != pend)
  256.     {
  257.       if (b - bufp->buffer > bufp->allocated - 10)
  258.     /* Note that EXTEND_BUFFER clobbers c */
  259.     EXTEND_BUFFER;
  260.  
  261.       PATFETCH (c);
  262.  
  263.       switch (c)
  264.     {
  265.     case '$':
  266.       if (obscure_syntax & RE_TIGHT_VBAR)
  267.         {
  268.           if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p != pend)
  269.         goto normal_char;
  270.           /* Make operand of last vbar end before this `$'.  */
  271.           if (fixup_jump)
  272.         store_jump (fixup_jump, jump, b);
  273.           fixup_jump = 0;
  274.           PATPUSH (endline);
  275.           break;
  276.         }
  277.  
  278.       /* $ means succeed if at end of line, but only in special contexts.
  279.         If randomly in the middle of a pattern, it is a normal character. */
  280.       if (p == pend || *p == '\n'
  281.           || (obscure_syntax & RE_CONTEXT_INDEP_OPS)
  282.           || (obscure_syntax & RE_NO_BK_PARENS
  283.           ? *p == ')'
  284.           : *p == '\\' && p[1] == ')')
  285.           || (obscure_syntax & RE_NO_BK_VBAR
  286.           ? *p == '|'
  287.           : *p == '\\' && p[1] == '|'))
  288.         {
  289.           PATPUSH (endline);
  290.           break;
  291.         }
  292.       goto normal_char;
  293.  
  294.     case '^':
  295.       /* ^ means succeed if at beg of line, but only if no preceding pattern. */
  296.  
  297.       if (laststart && p[-2] != '\n'
  298.           && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
  299.         goto normal_char;
  300.       if (obscure_syntax & RE_TIGHT_VBAR)
  301.         {
  302.           if (p != pattern + 1
  303.           && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
  304.         goto normal_char;
  305.           PATPUSH (begline);
  306.           begalt = b;
  307.         }
  308.       else
  309.         PATPUSH (begline);
  310.       break;
  311.  
  312.     case '+':
  313.     case '?':
  314.       if (obscure_